import Util.ColorNode;
import Util.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 二叉树先序遍历
 */
public class preOrder {

    /**
     * 递归实现
     * @param root
     * @return
     */
    public List<Integer> preOrderTraversal1(TreeNode root){
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }

    private void helper(TreeNode root, List<Integer> res){
        res.add(root.val);
        if (root.left != null){
            helper(root.left, res);
        }
        if (root.right != null){
            helper(root.right, res);
        }
    }


    /**
     * 非递归，颜色标记法
     * flag为0表示是新节点，为1表示节点已访问过；
     * 如果遇到flag为0，则将其标记为1，然后将右子节点、左子节点、自身依次入栈；（pre、in、post都是一样的道理）
     * 如果遇到flag为1，则将节点输出。
     * @param root
     * @return
     */
    public List<Integer> preOrderTraversal2(TreeNode root){
        List<Integer> res = new ArrayList<>();
        Stack<ColorNode> stack = new Stack<>();
        stack.push(new ColorNode(root, 0));

        while (!stack.isEmpty()){
            ColorNode cur = stack.pop();
            if (cur.flag == 0){
                if (cur.node.right != null){
                    stack.push(new ColorNode(cur.node.right, 0));
                }
                if (cur.node.left != null){
                    stack.push(new ColorNode(cur.node.left, 0));
                }
                stack.push(new ColorNode(cur.node, 1));
            }
            else {
                res.add(cur.node.val);
            }
        }
        return res;
    }
}
